package com.hardy.leetcode;

/**
 * 根据树的前序和中序遍历构造二叉树
 * User: Ruijie Date: 2016/9/2
 */
public class ConstructBinaryTreeFromPreorderAndInorder {
    public static class TreeNode{
        int val;
        TreeNode left;
        TreeNode right;
        public TreeNode(int val){
            this.val=val;
        }
    }
    public static TreeNode buildTree(int[] preorder, int[] inorder) {
        if(preorder.length!=inorder.length){
            return null;
        }
        if(preorder==null||inorder==null){
            return null;
        }
        return _buildTree(preorder,0,preorder.length-1,inorder,0,inorder.length-1);
    }

    private static TreeNode _buildTree(int[] preorder, int pStart, int pEnd, int[] inorder, int iStart, int iEnd) {
        if(pStart<=pEnd&&iStart<=iEnd){
            int index=getIndex(inorder,preorder[pStart]);
            TreeNode root=new TreeNode(preorder[pStart]);
            root.left=_buildTree(preorder,pStart+1,pStart+index-iStart,inorder,iStart,index-1);
            root.right=_buildTree(preorder,pEnd-(iEnd-index)+1,pEnd,inorder,index+1,iEnd);
            return root;
        }
        return null;
    }

    private static int getIndex(int[] inorder, int k) {
        int index=0;
        for(index=0;index<inorder.length;index++){
            if(inorder[index]==k){
                return index;
            }
        }
        return index;
    }
    private static void InOrderPrintTree(TreeNode root) {
        if(root!=null){
            InOrderPrintTree(root.left);
            System.out.print(root.val+"  ");
            InOrderPrintTree(root.right);
        }
    }

    public static void main(String[] args) {
        int[] preOrder={4,2,1,3,6,5,7};
        int[] inOrder={1,2,3,4,5,6,7};
        InOrderPrintTree(buildTree(preOrder,inOrder));
    }

}
